// 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

#include<bits/stdc++.h>
using namespace std;

// 手撕快排

// 执行用时：
// 24 ms
// , 在所有 C++ 提交中击败了
// 89.63%
// 的用户
// 内存消耗：
// 18.8 MB
// , 在所有 C++ 提交中击败了
// 36.12%
// 的用户


class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int> res;
        int len = arr.size();
        if(len<k){
            return res;
        }
        if(len==k){
            return arr;
        }
        fastSort(arr,0,arr.size());
        for(int i=0;i<k;++i){
            res.emplace_back(arr[i]);
        }
        return res;
    }

    void fastSort(vector<int>& arr,int left,int right){
        if(left+1>=right){
            return;
        }
        // 基准点
        int p = arr[left];
        int t_left = left;
        int t_right = right-1;
        while(t_left<t_right){

            while(t_left<t_right && arr[t_right]>=p){
                --t_right;
            }
            arr[t_left] = arr[t_right];
            while(t_left<t_right && arr[t_left]<=p){
                ++t_left;
            }
            arr[t_right] = arr[t_left];
        }
        // 中间点,已排序
        arr[t_left] = p; 
        fastSort(arr,left,t_left);
        fastSort(arr,t_left+1,right);
    }
};